package linkedlist.other;

import linkedlist.Node;
import linkedlist.iterator.LoopIterator;

/**
 * @Author wangtengyu
 * @Create 2018-09-06-12:22 复杂链表的赋值 1.第一种方式，第一次遍历把顺序的节点全复制了，第二次遍历查看有无随机指向 没有，两个链表同时指向下一个，
 * 有的话，原链表从头遍历链表，记录找到该节点需要几步，然后在复制的链表中复制  时间复杂度o（n2）
 *
 * 2.第二种方式，第一次遍历把顺序节点全复制了，并且添加到hash中，A对应A+这样，如果A找到了随机指向B，那么对应A+的随机指向就是B+，通过hash表得到B+，然后设置到A+上 空间换时间
 * 空间复杂度o（n）的哈希表，总体时间复杂度o（n)
 *
 * 3.第三种方式
 */
public class ComplexCopy {

  /**
   * 克隆基础节点
   */
  public Node cloneNodes(Node head) {
    if (head == null) {
      return null;
    }

    Node oldHead = head;
    while (oldHead != null) {
      Node cloneHead = new Node();
      cloneHead.setData(oldHead.getData());
      cloneHead.setNext(oldHead.getNext());
      oldHead.setNext(cloneHead);
      oldHead = cloneHead.getNext();
    }
    return head;
  }

  /**
   * 克隆随机节点
   */
  public Node cloneRandom(Node head) {

    if (head == null) {
      return null;
    }
    Node oldHead = head;
    while (oldHead != null) {
      Node cloneHead = oldHead.getNext();
      //原列表有随机指向
      if (oldHead.getRandom() != null) {
        cloneHead.setRandom(oldHead.getRandom().getNext());
      }
      oldHead = cloneHead.getNext();
    }
    return head;
  }

  /**
   * 拆成正常的两个链表
   */
  public Node reConnectNodes(Node head) {
    if (head == null) {
      return null;
    }
    Node oldHead = head;
    Node cloneHead = null;
    Node cloneNode = null;

    if (oldHead != null) {
      cloneHead = oldHead.getNext();
      cloneNode = oldHead.getNext();
      oldHead.setNext(cloneNode.getNext());
      oldHead = oldHead.getNext();
    }
    while (oldHead != null) {
      cloneNode.setNext(oldHead.getNext());
      cloneNode = oldHead.getNext();
      oldHead.setNext(cloneNode.getNext());
      oldHead = oldHead.getNext();
    }
    return cloneHead;

  }


  public static void main(String[] args) {
    Node A = new Node("A");
    Node B = new Node("B");
    Node C = new Node("C");
    Node D = new Node("D");
    Node E = new Node("E");
    A.setNext(B);
    B.setNext(C);
    C.setNext(D);
    D.setNext(E);
    E.setNext(null);
    A.setRandom(C);
    C.setRandom(B);
    D.setRandom(E);

    ComplexCopy complexCopy = new ComplexCopy();
    Node clonehead = complexCopy.cloneNodes(A);
    clonehead = complexCopy.cloneRandom(clonehead);
    clonehead = complexCopy.reConnectNodes(A);

    System.out.println(clonehead.getData());
    System.out.println(clonehead.getNext().getData());
    System.out.println(clonehead.getRandom().getData());
    while (clonehead != null) {
      System.out.println("node data is" + clonehead.getData());
      if (clonehead.getRandom() != null) {
        System.out.println("node random is node" + clonehead.getRandom().getData());
      }
      clonehead = clonehead.getNext();
    }


  }
}
